//
// Created by Administrator on 2024-2-20
// 分大于,小于等于区 以第一个数字为准
//

#include <iostream>
#include <vector>
#include "arrUtil.h"

using namespace std;

int netherlands(vector<int> &vector, int l, int r);

void quick_sort(vector<int> &v, int l, int r);

int main()
{
    vector<int> arr = {7, 2, 9, 3, 6, 3, 6, 5, 4};
//    arr={7,6,5,9,6};
//    arr={5,6};
//    arr={2,3,3};
//    arr={2,3};
//    arr={2};
//    netherlands(arr, 0, arr.size() - 1);
//    printVector(arr);
    randVector(arr, 1000);
    quick_sort(arr, 0, arr.size() - 1);
    cout << checkSortVector(arr);
    return 0;
}

void quick_sort(vector<int> &v, int l, int r)
{
    if (l < r)
    {
        int mid = netherlands(v, l, r);
        quick_sort(v, l, mid - 1);
        quick_sort(v, mid + 1, r);
    }
}

int netherlands(vector<int> &v, int l, int r)
{
    int cur = v[l], less_equal = l - 1;
    for (int i = l; i <= r; ++i)
    {
        if (v[i] <= cur)
        {
            ++less_equal;
            swap(v[less_equal], v[i]);
        }
    }
    swap(v[less_equal], v[l]);
//    cout<<endl<<less_equal<<endl;
    return less_equal;
}
